/*
 * 找出和至少为的子数组（连续的）
 * https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/
 * 双端队列
 */
int shortestSubarray(int* nums, int numsSize, int k){
    int res = INT_MAX;
    long pre_sum[numsSize + 1];
    int left = 0, right = 0;
    int deque[numsSize + 1];

    for (int i = 0; i < numsSize; i++) {
        pre_sum[i+1] = pre_sum[i] + nums[i]; // pre_sum[i] 为前i个元素的和
    }

    // pre_sum[j] - pre_sum[x] >= k; 且j - x为最小值
    for (int j = 0; j < numsSize + 1; j++) {
        // 保证队列为递增，才能保证j - x >= k
        while (left < right && pre_sum[j] <= pre_sum[deque[right - 1]]) {
            right--;
        }
        // pre_sum[j] - pre_sum[x] >= k
        while (left < right && pre_sum[j] >= pre_sum[deque[left]] + k) {
            int tmp = deque[left++];
            res = fmin(res, j - tmp); // 找出最小值
        }
        deque[right++] = j;
    }

    return (res != INT_MAX) ? res : -1;
}